//#region Common
// File: CsoGateway.Collections.Dictionary.js
// Version: 0.7.1.0
// Author: Pascal Dufresne
// Date: 2008-12-03
// Last update: 2009-05-25
// http://csogateway.codeplex.com
// http://csogateway.metaobjects.ca
// Copyright (C) 2010 Pascal Dufresne

/*
 * Register CsoGateway.Collections namespace. Import CsoGateway.System namespace.
 */
Type.registerNamespace("CsoGateway.Collections");
ImportNamespace(CsoGateway.System);

//#endregion Common

//#region Entry

/*
 * CsoGateway.Collections.Entry is a structure used to stored to key/value pair of a
 * CsoGateway.Collections.Dictionary. Since the Dictionary is using a chained list to
 * workaround collision, there is a next variable in Entry to hold a reference to
 * the next element in the chained list.
 *
 */
CsoGateway.Collections.Entry = function Entry(k, v, n)
{
	AssertArgumentNotNullOrUndefined(k, 'k in CsoGateway.Collections.Entry');
	AssertArgumentNotUndefined(v, 'v in CsoGateway.Collections.Entry');
	AssertArgumentNotUndefined(n, 'n in CsoGateway.Collections.Entry');
	
	this.key = k;
	this.value = v;
	this.next = (n ? n : null);
}

CsoGateway.Collections.Entry.registerClass('CsoGateway.Collections.Entry', CsoNative, Sys.IDisposable);

/*
 * End of CsoGateway.Collections.Entry definition
 */

//#endregion Entry
//#region Bucket

/*
 * CsoGateway.Collections.Bucket is a linked list holding key/value pairs of the
 * CsoGateway.Collections.Dictionary class.
 */

ImportType(CsoGateway.Collections.Entry);


CsoGateway.Collections.Bucket = function Bucket()
{	
	this.count = 0;
	this.first = null;
}

CsoGateway.Collections.Bucket.prototype.add = function(key, value)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.Bucket.prototype.add');
	AssertArgumentNotUndefined(value, 'value in CsoGateway.Collections.Bucket.prototype.add');
		
	if(this.first != null)
	{
		var old;
		for(var e = this.first; e != null; e = e.next)
		{	
			//Key is found
			if(e.key == key)
			{	
				old = e.value;
				e.value = value;
				return old;
			}
		}
	}
	
	// Bucket empty or key not found
	this.first = new Entry(key, value, this.first);
	this.count++;

	return null;
}

CsoGateway.Collections.Bucket.prototype.remove = function(key)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.Bucket.prototype.remove');

	if(this.first != null)
	{	
		for(var e = this.first, prev = null; e != null; prev = e, e = e.next)
		{	
			//Key is found
			if(e.key == key)
			{	
				if(prev == null)
					this.first = e.next; // It's the first element
				else
					prev.next = e.next; // Not the first element
				
				this.count--;
				
				return e.value; // return value removed
			}
		}
	}		
	
	return null; // return null if key not found
}

CsoGateway.Collections.Bucket.prototype.clear = function()
{	
	this.first = null;
	this.count = 0;
}
CsoGateway.Collections.Bucket.registerClass('CsoGateway.Collections.Bucket', CsoNative, Sys.IDisposable);

/*
 * End of CsoGateway.Collections.Bucket definition
 */

//#endregion Bucket
//#region Dictionary

/*
 * CsoGateway.Collections.Dictionary is an implementation of the 'Dictionary' abstract
 * data type. The underlying data structure used is a hashtable using as linked list
 * for collision resolution. It's interface is meant to resemble
 * that of the .NET class System.Collections.Generic.Dictionary<System.Object, System.Object> 
 *
 * The respect of its interface is strictly enforced. All method parameters
 * must be specified, they must be of the right type and within an acceptable
 * range of an exception is thrown.
 *
 * The hash codes are calculated using the CsoGateway.Collections.Hashing utility class.
 *
 * This class uses the MicrosoftAjax.js Type extensions.
 * It is build on top of the MicrosoftAjax.js library and cannot function without it.
 *
 * Contructor						'System.Collections.Generic.Dictionary<System.Object, System.Object>' equivalent
 * ----------						-----------------------------------------------------------
 *									
 * Dictionary()                     Dictionary()
 * Dictionary(only one args)        Dictionary(Int32)
 * Dictionary()(even # of args )    Dictionary(System.Collections.Generic.IDictionary<System.Object, System.Object>)
 *
 *
 * Methods                          'System.Collections.Generic.Dictionary<System.Object,System.Object>' equivalent
 * ----------						-----------------------------------------------------------
 * Count()                          Count
 * getItem(Object)                  Item{get;}
 * setItem(Object, Object)          Item{set;}
 * Keys()                           Keys
 * Values()                         Values
 * Add(Object, Object)              Add(System.Object, System.Object)
 * Clear()                          Clear()
 * ContainsKey(Object)              ContainsKey(System.Object)
 * ContainsValue(Object)            ContainsKey(System.Object)
 * Remove(Object)                   Remove(System.Object)
 * bucketFor                        -
 *
 */

ImportType(CsoGateway.Collections.Bucket);
ImportType(CsoGateway.Collections.Entry);
ImportType(CsoGateway.Collections.Hashing);

/*
 * Creates an instance of a CsoGateway.Collections.Dictionary. 
 * There are 3 ways to create a Dictionary object corresponding to 3 different constructor:
 *
 * - Dictionary()
 *		No arguments. A new empty Dictionary object is created with 32 buckets.
 *		Ex: Dictionary d = new Dictionary();
 * - Dictionary(capacity)
 *		1 arguments of type Number with a value between 1 and 4096. 
 *		A new empty Dictionary object is created with 2 times the capacity as the number of buckets,
 *		so that the initial load factor is 0.5
 * - Dictionary(key1, value1, key2, value2 ....)
 *		An even number of arguments of any type. 'Key' arguments cannot be null or undefined.
 *		If an odd number of arguments (other than 1) is given, an error is thrown.
 *		A new Dictionary object is created with a number of buckets equal to the number of arguments.
 *		Each key/value pair is then inserted in the Dictionary.
 *		Since there is 2 arguments per key/value pair, the number of buckets will be twice the initial
 *		number of elements in the Dictionary, making the initial load factor 0.5.
 */
CsoGateway.Collections.Dictionary = function Dictionary()
{
	// Default number if buckets is 32
	if(arguments.length == 0)
	{
		this.buckets = new Array(32);
		for(var i=0; i<this.buckets.length; ++i)
			this.buckets[i] = new Bucket();
	}
	else if(arguments.length == 1)
	{
		AssertArgumentIsNumberInRange(arguments[0], 1, 4096, 'capacity, 1st argument in CsoGateway.Collections.Dictionary constructor');
		
		// Initial load factor is 0.5 so number of buckets is 2x the capacity
		this.buckets = new Array(2 * arguments[0]);
		
		for(var i=0; i<this.buckets.length; ++i)
			this.buckets[i] = new Bucket();
	}
	else
	{
		if((arguments.length % 2) != 0)
			throw new Error('CsoGateway.Collections.Dictionary: The number of arguments passed to the constructor ' +
			'must be 0, 1 or an even number.');
	
		// Initial load factor is 0.5. Length of arguments is 2x number of elements.
		this.buckets = new Array(arguments.length);
		
		for(var i=0; i<this.buckets.length; ++i)
			this.buckets[i] = new Bucket();
		
		for(var i=0; i < arguments.length; i = i + 2)
		{
			this.setItem(arguments[i], arguments[i+1]);
		}
	}
}

/*
 * Gets the number of elements actually contained in the Dictionary.
 * Ref: System.Collection.Generic.Dictionary.Count 
 */
CsoGateway.Collections.Dictionary.prototype.Count =  function()
{
	var totalCount = 0;

	for(var i=0; i < this.buckets.length; ++i)
	{
		totalCount += this.buckets[i].count;
	}
	
	return totalCount;
}

/*
 * Gets the value associated with the specified key.
 * Ref: System.Collection.Generic.Dictionary.Item
 */
CsoGateway.Collections.Dictionary.prototype.getItem =  function(key)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.Dictionary.prototype.getItem');

	var bucket = this.bucketFor(key);
	
	for(var e = bucket.first; e != null; e = e.next)
		if(e.key == key)
			return e.value;

	return null;
}

/*
 * Sets the value associated with the specified key.
 * Ref: System.Collection.Generic.Dictionary.Item
 */
CsoGateway.Collections.Dictionary.prototype.setItem =  function(key, value)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.Dictionary.prototype.setItem');
	AssertArgumentNotUndefined(value, 'value in CsoGateway.Collections.Dictionary.prototype.setItem');
	
	return this.bucketFor(key).add(key, value);
}

/*
 * Gets an Array containing the keys in the Dictionary
 * Ref: System.Collection.Generic.Dictionary.Keys
 */
CsoGateway.Collections.Dictionary.prototype.Keys =  function()
{
	var keyArray = new Array();
	
	var bucket, e;
	for(var i=0; i < this.buckets.length; i++)
	{
		bucket = this.buckets[i];
		
		for(e = bucket.first; e != null; e = e.next)
			keyArray[keyArray.length] = e.key;
	}
	
	return keyArray;
}

/*
 * Gets an Array containing the values in the Dictionary
 * Ref: System.Collection.Generic.Dictionary.Values
 */
CsoGateway.Collections.Dictionary.prototype.Values =  function()
{
	var valueArray = new Array();
	
	var bucket, e;
	for(var i=0; i < this.buckets.length; i++)
	{
		bucket = this.buckets[i];
		
		for(e = bucket.first; e != null; e = e.next)
			valueArray[valueArray.length] = e.value;
	}
	
	return valueArray;
}

/*
 * Adds the key value pair to the Dictionary. Throws an error if the key is already in the Dictionary
 * and has a value associated with it.
 * Ref: System.Collection.Generic.Dictionary.Add
 */
CsoGateway.Collections.Dictionary.prototype.Add =  function(key, value)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.Dictionary.prototype.Add');
	
	if(this.ContainsKey(key) && this.getItem(key) != null)
		throw new Error('CsoGateway.Collections.Dictionary.prototype.Add: There is already a value associated with the specified key: ' + key.toString());

	this.setItem(key, value);
}

/*
 * Removes all keys and values from the Dictionary.
 * Ref: System.Collection.Generic.Dictionary.Clear
 */
CsoGateway.Collections.Dictionary.prototype.Clear =  function()
{
	for(var i=0; i<this.buckets.length; ++i)
	{
		this.buckets[i].clear();
	}
}

/*
 * Determines whether the Dictionary contains the specified key.
 * Ref: System.Collection.Generic.Dictionary.ContainsKey
 */
CsoGateway.Collections.Dictionary.prototype.ContainsKey =  function(key)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.Dictionary.prototype.ContainsKey');
	
	var bucket = this.bucketFor(key);
	
	for(var e = bucket.first; e != null; e = e.next)
		if(e.key === key)
			return true;
			
	return false;
}

/*
 * Determines whether the Dictionary contains a specific value.
 * Ref: System.Collection.Generic.Dictionary.ContainsValue
 */
CsoGateway.Collections.Dictionary.prototype.ContainsValue = function(value)
{
	AssertArgumentNotUndefined(value, 'value in CsoGateway.Collections.Dictionary.prototype.ContainsValue');
	
	for(var i=0; i<this.buckets.length; ++i)
	{
		for(var e = this.buckets[i].first; e != null; e = e.next)
			if(e.value === value)
				return true;
	}
			
	return false;
}

/*
 * Remove the value with the specific key from the Dictionary.
 * This function return true is the item was found and removed and false otherwise.
 * Ref: System.Collection.Generic.Dictionary.Remove
 */
CsoGateway.Collections.Dictionary.prototype.Remove = function(key)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.Dictionary.prototype.Remove');
	
	return (this.bucketFor(key).remove(key) != null);
}

/*
 * Return the bucket for a given key object. Use the hashing function
 * CsoGateway.Collections.Hashing.Hash to compute the hash code.
 * 
 */
CsoGateway.Collections.Dictionary.prototype.bucketFor = function(keyObj)
{	
	return this.buckets[Hashing.Hash(keyObj) % this.buckets.length];
}

CsoGateway.Collections.Dictionary.registerClass('CsoGateway.Collections.Dictionary', CsoNative, Sys.IDisposable);

/*
* End of CsoGateway.Collections.Dictionary definition
*/

//#endregion Dictionary